package com.wxg.algorithm.chapter04;

public class IndexMaxHeap<T extends Comparable> {

    private T[] data;

    private int[] indexes;

    private int[] reverse;

    private int capacity;

    private int count;

    public IndexMaxHeap(int capacity){
        this.capacity = capacity;
        data = (T[]) new Comparable[capacity + 1]; // 二叉堆-索引从`1`开始
        indexes = new int[capacity + 1];
        reverse = new int[capacity + 1];
        count = 0;
    }

    public int size(){
        return count;
    }

    public boolean isEmpty(){
        return count == 0;
    }

    // 传入的 i 对用户而言, 是从索引 0 开始的
    public void insert(int i, T item){
        if(count+1 > capacity){
            throw new RuntimeException("超出容量");
        }
        if ( i + 1 < 1 || i + 1 > capacity ){
            throw new RuntimeException("传入的索引错误");
        }

        i += 1;
        data[i] = item;
        indexes[count+1] = i;
        reverse[i] = count + 1;

        count++;
        shiftUp( count );
    }

    public T extractMax(){
        if(count <= 0){
            throw new RuntimeException("已经没有元素了");
        }
        T ret = data[indexes[1]];

        swapInt(indexes, 1, count);
        reverse[indexes[1]] = 1;
        reverse[indexes[count]] = 0;
        count --;

        shiftDown(1);

        return ret;
    }

    public int extractMaxIndex(){
        if(count <= 0){
            throw new RuntimeException("已经没有元素了");
        }

        int ret = indexes[1] - 1;

        swapInt(indexes, 1, count);
        reverse[indexes[1]] = 1;
        reverse[indexes[count]] = 0;
        count --;

        shiftDown(1);

        return ret;
    }

    public boolean contain(int i){
        if( i+1 < 1 || i+1 > capacity){
            throw new RuntimeException("下标越界");
        }
        return reverse[i+1] != 0;
    }

    public T getItem(int i){
        if(!contain(i)){
            throw new RuntimeException("非法操作, 不包含此元素");
        }

        return data[i+1];
    }

    public void change(int i, T newItem){
        if(!contain(i)){
            throw new RuntimeException("非法操作, 不包含此元素");
        }

        i += 1;
        data[i] = newItem;

        // 找到 indexes[j] == i, j 表示 data[i] 在堆中的位置
//        for (int j = 1; j <= count; j++){
//            if(indexes[j] == i){
//                shiftUp(j);
//                shiftDown(j);
//                break;
//            }
//        }
        int j = reverse[i];
        shiftUp(j);
        shiftDown(j);
    }

    private void shiftDown(int k) {
        while ( 2*k <= count ){
            int j = 2*k; //
            if( j + 1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) > 0 ){
                j += 1;
            }

            if( data[indexes[k]].compareTo(data[indexes[j]]) >= 0 ){ // 这里`==0`时也可以break吧?
                break;
            }

            swapInt(indexes, k, j);
            reverse[indexes[k]] = k;
            reverse[indexes[j]] = j;
            k = j;
        }
    }

    private void shiftUp(int k) {
        while ( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0){
            swapInt(indexes, k/2, k);
            reverse[indexes[k/2]] = k/2;
            reverse[indexes[k]] = k;
            k /= 2;
        }
    }

    private void swapInt(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    private void swap(T[] arr, int a, int b) {
        T temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
